package com.linyaonan.leetcode.medium._2461;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
 *
 * 子数组的长度是 k，且
 * 子数组中的所有元素 各不相同 。
 * 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
 *
 * 子数组 是数组中一段连续非空的元素序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,5,4,2,9,9,9], k = 3
 * 输出：15
 * 解释：nums 中长度为 3 的子数组是：
 * - [1,5,4] 满足全部条件，和为 10 。
 * - [5,4,2] 满足全部条件，和为 11 。
 * - [4,2,9] 满足全部条件，和为 15 。
 * - [2,9,9] 不满足全部条件，因为元素 9 出现重复。
 * - [9,9,9] 不满足全部条件，因为元素 9 出现重复。
 * 因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。
 * 示例 2：
 *
 * 输入：nums = [4,4,4], k = 3
 * 输出：0
 * 解释：nums 中长度为 3 的子数组是：
 * - [4,4,4] 不满足全部条件，因为元素 4 出现重复。
 * 因为不存在满足全部条件的子数组，所以返回 0 。
 *
 *
 * 提示：
 *
 * 1 <= k <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^5
 *
 * @author: Lin
 * @date: 2024/10/7
 */
public class MaximumSumOfDistinctSubarrays {

    /**
     * 滑动窗口
     * 会存在超时
     * @param nums
     * @param k
     * @return
     */
    public long maximumSubarraySum(int[] nums, int k) {
        long max = 0L;
        // 用于记录数值是否已出现
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        long add = 0L;
        for (int i = 0; i < nums.length; i++) {
            add += nums[i];
            map.merge(nums[i], 1, Integer::sum);

            count++;
            if (count == k) {
                if (map.size() == k) {
                    max = Math.max(max, add);
                }
                count--;
                add -= nums[i - k + 1];
                // 把等于k - 1的元素数量减一，为0则删除
                if (map.merge(nums[i - k + 1], -1, Integer::sum) == 0) {
                    map.remove(nums[i - k + 1]);
                }
            }
        }

        return max;
    }

}
